1000

A+B Problem

极高精度版本的qwq a+b

Two integer a,b (0<=a,b<=10)

Output a+b

1 2

3

0

国际惯例题，相关请看FAQ

2017-11-27 16:50:02

1

10

N

77

175

0

1102

【贪心】NOIP_2004.TG2:合并果子

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入文件中包括两行：第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。 第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。

输出文件包括一行：这一行只包含一个整数，也就是最小的体力耗费值。（输入数据保证这个值小于2³¹。）

3 1 2 9

15

0

【数据规模】 对于30％的数据，保证有n<=1000： 对于50％的数据，保证有n<=5000； 对于全部的数据，保证有n<=10000。

NOIP_2004.TG2:合并果子

2017-06-02 20:54:12

1

64

N

66

139

0

1101

NOIP_2004.TG1:津津的储蓄计划

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。 为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。 例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。 津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。 现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。

输出文件save.out包括一行，这一行只包含一个整数。 如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月； 否则输出到2004年年末津津手中会有多少钱。

【样例输入1】 290 230 280 200 300 170 340 50 90 80 200 60 【样例输入2】 290 230 280 200 300 170 330 50 90 80 200 60

【样例输出1】 -7 【样例输出2】 1580

0

NOIP_2004.TG1:津津的储蓄计划

2017-03-21 18:01:55

1

64

N

5

15

0

1001

USACO_1.1-1:你的飞碟在这儿！

科学家们在研究彗星后惊讶地发现，在每一个慧星后面都有一个不明飞行物UFO。 这些不明飞行物时常来带走来自地球上的一些支持者。不幸地，他们的空间在每次旅行只能带上一群支持者。 他们要做的是用一种聪明的方案让某个支持彗星UFO的团体都被慧星带走。他们为每个慧星起了一个名字，通过这些名字来决定一个团体是不是特定的慧星带走。 那个相配方案的细节是这样的: 所有团体的名字和慧星的名字都以下列各项方式转换成一个数字: 这个最后的数字代表名字中所有字母的信息，"A" 是 1 和 "Z" 是 26。 举例来说，团体 "USACO" 会是 21*19*1*3*15=17955 。 如果团体的数字 mod 47 等于慧星的数字 mod 47,那么你要告诉这个团体：准备好行李，走吧 ! 现在，你要写一个程序来通过团体的名字和彗星的名字来决定一个组是否应该与在那一颗慧星后面的不明飞行物搭配。 写一个程序读入慧星的名字和团体的名字，如果搭配打印"GO"否者打印"STAY" 团体的名字和慧星的名字将会是没有空格或标点的一串大写字母（不超过6个字母）。

第 1 行: 彗星的名字（一个长度为1到6的字符串） 第 2 行: 团体的名字（一个长度为1到6的字符串）

只有一行----"STAY"或"GO".

ABSTAR USACO

STAY

0

http://ace.delos.com/usacoprob2?a=XogK3Q5R3CD&S=ride

USACO 1.1-1

2017-03-18 10:42:56

1

64

N

29

57

0

1002

USACO_1.1-2:贪婪的礼物送礼者

对于一群要互送礼物的朋友，你要确定每个人送出的礼物比收到的多多少(and vice versa for those who view gift giving with cynicism)。 在这一个问题中，每个人都准备了一些钱来送礼物，而这些钱将会被平均分给那些将收到他的礼物的人。 然而，在任何一群朋友中，有些人将送出较多的礼物(可能是因为有较多的朋友)，有些人有准备了较多的钱。 给出一群朋友， 没有人的名字会长于 14 字符，给出每个人将花在送礼上的钱，和将收到他的礼物的人的列表，请确定每个人收到的比送出的钱多的数目。

第 1 行: 人数NP,2<= NP<=10 第 2到 NP+1 行:这NP个在组里人的名字　一个名字一行 第NP＋2到最后： 这里的NP段内容是这样组织的： 第一行是将会送出礼物人的名字。 第二行包含二个数字:　第一个是原有的钱的数目（在0到2000的范围里），第二个NGi是将收到这个送礼者礼物的人的个数 如果 NGi 是非零的, 在下面 NGi 行列出礼物的接受者的名字，一个名字一行。

输出 NP 行 每行是一个的名字加上空格再加上收到的比送出的钱多的数目。 对于每一个人，他名字的打印顺序应和他在输入的2到NP＋1行中输入的顺序相同。所有的送礼的钱都是整数。 每个人把相同数目的钱给每位要送礼的朋友，而且尽可能多给，不能给出的钱被送礼者自己保留。

5 dave laura owen vick amr dave 200 3 laura owen vick owen 500 1 dave amr 150 2 vick owen laura 0 2 amr vick vick 0 0

dave 302 laura 66 owen -359 vick 141 amr -150

0

测试系统是 Linux 符合标准的 Unix 的协定。 用'\n'作为行的结束。这和　Windows 系统用'\n' 和 '\r'作为行的结束是不同的。 你的程序不要被这困住了。

USACO 1.1-2

2017-03-18 10:45:52

1

64

N

8

10

0

1003

USACO_1.1-3:黑色星期五

13号又是星期五是一个不寻常的日子吗?13号在星期五比在其他日少吗?为了回答这个问题,写一个程序来计算在n年里13日落在星期一,星期二......星期日的次数.这个测试从1900年1月1日到1900+n-1年12月31日.n是一个非负数且不大于400. 这里有一些你要知道的: 1900年1月1日是星期一.4,6,11和9月有30天.其他月份除了2月都有31天.闰年2月有29天,平年2月有28天.年份可以被4整除的为闰年(1992=4*498 所以 1992年是闰年,但是1990年不是闰年)以上规则不适合于世纪年.可以被400整除的世纪年为闰年,否则为平年.所以,1700,1800,1900和2100年是平年,而2000年是闰年.请不要预先算好数据!

一个整数n.

七个在一行且相分开的整数,它们代表13日是星期六,星期日,星期一.....星期五的次数.

20

36 33 34 33 35 35 34

0

USACO 1.1-3

2017-03-18 10:49:35

1

64

N

9

10

0

1004

USACO_1.1-4:破碎的项链

你有一条由N个红色的，白色的，或蓝色的珠子组成的项链(3<=N<=350)，珠子是随意安排的。 这里是 n=29 的二个例子: <img src="/JudgeOnline/upload/image/20170720/20170720151431_18434.png" alt="" /> 第一和第二个珠子在图片中已经被作记号。 图片 A 中的项链可以用下面的字符串表示： brbrrrbbbrrrrrbrrbbrbbbbrrrrb . 假如你要在一些点打破项链,展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事。(颜色可能与在这之前收集的不同) 确定应该在哪里打破项链来收集到最大多数的数目的子。 Example 举例来说，在图片 A 中的项链，可以收集到8个珠子,在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链。 在一些项链中，包括白色的珠子如图片 B 所示。 当收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。 表现项链的字符串将会包括三符号 r ， b 和 w 。 写一个程序来确定从一条被供应的项链最大可以被收集珠子数目。

第 1 行: N, 珠子的数目 第 2 行: 一串度为N的字符串, 每个字符是 r ， b 或 w。

单独的一行包含从被供应的项链可以被收集的珠子数目的最大值。

29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

11

0

USACO_1.1-4

2017-07-20 15:14:42

1

64

N

5

13

0

1005

USACO_1.2-1:挤牛奶

三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300时刻(从5点开始计时，秒为单位)给他的牛挤奶，一直到1000时刻。第二个农民在700时刻开始，在 1200时刻结束。第三个农民在1500时刻开始2100时刻结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300时刻到1200时刻)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200时刻到1500时刻)。 你的任务是编一个程序，读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位): 最长至少有一人在挤奶的时间段。 最长的无人挤奶的时间段。

Line 1: 一个整数N。 Lines 2..N+1: 每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。

一行，两个整数，即题目所要求的两个答案。

3 300 1000 700 1200 1500 2100

900 300

0

USACO_1.2-1:

2017-03-18 11:03:39

1

64

N

8

10

0

1006

USACO_1.2-2:方块转换

一块N x N（1<=N<=10）正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式： 1：转90度：图案按顺时针转90度。 2：转180度：图案按顺时针转180度。 3：转270度：图案按顺时针转270度。 4：反射：图案在水平方向翻转（形成原图案的镜像）。 5：组合：图案在水平方向翻转，然后按照1-3之一转换。 6：不改变：原图案不改变。 7：无效转换：无法用以上方法得到新图案。 如果有多种可用的转换方法，请选择序号最小的那个。

第一行： 单独的一个整数N。 第二行到第N+1行： N行每行N个字符（不是“@”就是“-”）；这是转换前的正方形。 第N+2行到第2*N+1行： N行每行N个字符（不是“@”就是“-”）；这是转换后的正方形。

单独的一行包括1到7之间的一个数字（在上文已描述）表明需要将转换前的正方形变为转换后的正方形的转换方法。

3 @-@ --- @@- @-@ @-- --@

1

0

USACO_1.2-2

2017-03-18 11:04:00

1

64

N

4

9

0

1007

USACO_1.2-4:回文平方数

回文数是指从左向右念和从右像做念都一样的数。如12321就是一个典型的回文数。 给定一个进制B(2<=B<=20十进制)，输出所有的大于等于1小于等于300且它的平方用B进制表示时是回文数的数。用’A’,’B’……表示10，11等等。

共一行，一个单独的整数B(B用十进制表示)。

每行两个数字，第二个数是第一个数的平方，且第二个数是回文数。(注意:这两个数都应该在B那个进制下)

10

1 1 2 4 3 9 11 121 22 484 26 676 101 10201 111 12321 121 14641 202 40804 212 44944 264 69696

0

USACO_1.2-4

2017-03-18 11:04:00

1

64

N

5

7

0

1008

USACO_1.2-5:双重回文数

如果一个数从左往右读和从右往左读都是一样，那么这个数就叫做“回文数”。例如，12321就是一个回文数，而77778就不是。当然，回文数的首和尾都应是非零的，因此0220就不是回文数。 事实上，有一些数（如21），在十进制时不是回文数，但在其它进制（如二进制时为10101）时就是回文数。 编一个程序，从文件读入两个十进制数N (1 <= N <= 15)S (0 < S < 10000)然后找出前N个满足大于S且在两种或两种以上进制（二进制至十进制）上是回文数的十进制数，输出到文件上。 本问题的解决方案不需要使用大于4字节的整型变量。

只有一行，用空格隔开的两个数N和S。

N行, 每行一个满足上述要求的数，并按从小到大的顺序输出。

3 25

26 27 28

0

USACO_1.2-5

2017-03-18 11:04:00

1

64

N

2

3

0

1009

USACO_1.3-1:混合牛奶

牛奶包装是一个如此低利润的生意,所以尽可能低的控制初级产品(牛奶)的价格变的十分重要。请帮助快乐的牛奶制造公司(Merry Milk Makers')以可能的最廉价的方式取得他们所需的牛奶。快乐的牛奶制造公司从一些农民那购买牛奶，每个农民卖给牛奶制造公司的价格不一定相同。而且,如一只母牛一天只能生产一定量的牛奶,农民每一天只有一定量的牛奶可以卖。每天,快乐的牛奶制造公司从每个农民那购买一定量的牛奶,少于或等于农民所能提供的最大值。给出快乐牛奶制造公司的每日的牛奶需求,连同每个农民的可提供的牛奶量和每加仑的价格,请计算快乐的牛奶制造公司所要付出钱的最小值。 注意:每天农民生产的牛奶的总数对快乐的牛奶制造公司来说足够的。

第 1 行:二个整数, N 和 M。 第一个数值,N,(0<= N<=2,000,000)是快乐的牛奶制造者的一天需要牛奶的数量。 第二个数值,M,(0<= M<=5,000)是提供牛奶的农民个数。 第 2 到 M+1 行:每行二个整数,Pi 和 Ai。 Pi(0<= Pi<=1,000) 是农民 i 牛奶的价格。 Ai(0 <= Ai <= 2,000,000)是农民 i 一天能卖给快乐的牛奶制造者的牛奶数量。

单独的一行包含单独的一个整数，表示快乐的牛奶制造者拿到所需的牛奶所要的最小费用。

100 5 5 20 9 40 3 10 8 80 6 30

630

0

USACO_1.3-1

2017-03-18 11:04:00

1

64

N

3

5

0

1010

USACO_1.3-2:修理牛棚

在一个暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 剩下的牛一个紧挨着另一个被排成一行来过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,农民约翰很快在牛棚之前竖立起新的木板。 他的新木材供应者将会供应他任何他想要的长度,但是供应者只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。 给出 M(1<= M<=50),可能买到的木板最大的数目;S(1<= S<=200),牛棚的总数;C(1 <= C <=S) 牛棚里牛的数目,和牛所在的牛棚的编号stall_number(1 <= stall_number <= S),计算拦住所有有牛的牛棚所需木板的最小总长度。 输出所需木板的最小总长度作为的答案。

第 1 行: M ， S 和 C(用空格分开) 第 2 到 C+1行: 每行包含一个整数，表示牛所占的牛棚的编号。

单独的一行包含一个整数表示所需木板的最小总长度。

4 50 18 3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43

25

0

[ 一种最优的安排是用板拦住牛棚3-8,14-21,25-31,40-43.]

USACO_1.3-2

2017-03-18 11:04:01

1

64

N

3

4

0

1011

USACO_1.3-3:calfflac

据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最棒的回文。你的工作就是去寻找这些牛制造的奇观(最棒的回文)。 在寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母'A'-'Z'和'a'-'z'。要你寻找的最长的回文的文章是一个不超过20,000个字符的字符串。 我们将保证最长的回文不会超过2,000个字符(在除去标点符号、空格之前)。

输入文件不会超过20,000字符。这个文件可能一行或多行，但是每行都不超过80个字符(不包括最后的换行符)。

输出的第一行应该包括找到的最长的回文的长度。 下一行或几行应该包括这个回文的原文（没有除去标点符号、空格），把这个回文输出到一行或多行（如果回文中包括换行符）。 如果有多个回文长度都等于最大值，输出最前面出现的那一个。

Confucius say:Madam,I'm Adam.

11 Madam,I'm Adam

0

USACO_1.3-3

2017-03-18 11:12:04

1

64

N

2

3

0

1012

USACO_1.3-4:牛式

<p> 下面是一个乘法竖式，如果用我们给定的那n个数字来取代*。 并且可以使式子成立的话，我们就叫这个式子牛式。 <img src="/JudgeOnline/upload/image/20170720/20170720152039_78748.jpg" alt="" /> </p> <p> 数字只能取代*号出现位置，当然第一位不能为0。 写一个程序找出所有的牛式。所选用数字均来自于集合{1,2,3,4,5,6,7,8,9}。 </p>

Line 1:你将可能使用的数字的个数n。 Line 2:N个用空格分开，在你的程序中允许使用的数字（每个数字都∈{1,2,3,4,5,6,7,8,9}）。

共一行，一个数字。表示牛式的总数。

5 2 3 4 6 8

1 符合条件的牛式如下： 2 2 2 x 2 2 ------ 4 4 4 4 4 4 --------- 4 8 8 4

0

USACO_1.3-4

2017-07-20 15:20:47

1

64

N

0

3

0

1013

USACO_1.4-1:铺放矩形块(IOI 95)

<p> 给定4个矩形块，找出一个最小的封闭矩形将这4个矩形块放入，但不得相互重叠。所谓最小矩形指该矩形面积最小。 <img src="/JudgeOnline/upload/image/20170720/20170720151830_62930.jpg" alt="" /> </p> <p> 所有4个矩形块的边都与封闭矩形的边相平行，图1示出了铺放4个矩形块的6种方案。这6种方案是仅可能的基本铺放方案。因为其它方案能由基本方案通过旋转和镜像反射得到。 可能存在满足条件且有着同样面积的各种不同的封闭矩形，你应该输出所有这些封闭矩形的边长。 </p>

共有4行。每一行用两个正整数来表示一个给定的矩形块的两个边长。矩形块的每条边的边长范围最小是1，最大是50。

总行数为解的总数加1。第一行是一个整数，代表封闭矩形的最小面积（子任务A）。接下来的每一行都表示一个解，由数P和数Q来表示，并且P≤Q（子任务B）。这些行必须根据P的大小按升序排列，P小的行在前，大的在后。且所有行都应是不同的。

1 2 2 3 3 4 4 5

40 4 10 5 8

0

USACO_1.4-1

2017-07-20 15:18:44

1

64

N

2

3

0

1014

USACO_1.4-2:The Clocks 时钟IOI'94-Day 2

<p> 考虑将如此安排在一个 3 x3 行列中的九个时钟: <img src="/JudgeOnline/upload/image/20170720/20170720152224_63716.gif" alt="" />  </p> <p> 目标要找一个最小的移动顺序次将所有的指针指向12点。下面原表格列出了9种不同的旋转指针的方法，每一种方法都叫一次移动。选择1到9号移动方法，将会使在表格中对应的时钟的指针顺时针旋转90度。 移动方法 受影响的时钟 <img src="/JudgeOnline/upload/image/20170720/20170720152442_26882.png" alt="" /> </p> <p>  Example <img src="/JudgeOnline/upload/image/20170720/20170720152847_74763.png" alt="" /> [但这可能不是正确的方法，请看下面] </p>

第1-3行: 三个空格分开的数字，每个数字表示一个时钟的初始时间，3,6,9,12。数字的含意和上面第一个例子一样。

单独的一行包括一个用空格分开的将所有指针指向12:00的最短移动顺序的列表。 如果有多种方案，输出那种使的连接起来数字最小的方案。(举例来说5 2 4 6 < 9 3 1 1)。

9 9 12 6 6 6 6 3 6

4 5 8 9

0

本题测试数据USACO共给出了9组，不过只通过了5组，因而只放了5组测试数据，还有4组数据为Wrong Answer，具体原因现在不明！ (注明：我的程序是在USACO上没有问题的，数据全部通过！)

USACO_1.4-2

2017-07-20 15:28:56

50

640

N

2

3

0

1015

USACO_1.4-3:ArithmeticProgressions等差数列

一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的数列。 在这个问题中a是一个非负的整数，b是正整数。写一个程序来找出在双平方数集合S中长度为n的等差数列。双平方数集合是所有能表示成p^2＋q^2的数的集合。

第一行: N(3<= N<=25),要找的等差数列的长度。 第二行: M(1<= M<=250),搜索双平方数的上界0 <= p,q <= M。

如果没有找到数列,输出`NONE'。 如果找到了，输出一行或多行, 每行由于二个整数组成:a,b。 这些行应该先按b排序再按a排序。 所求的等差数列将不会多于10,000个。

5 7

1 4 37 4 2 8 29 8 1 12 5 12 13 12 17 12 5 20 2 24

0

TIME LIMIT: 5 秒

USACO_1.4-3

2017-03-18 11:12:04

15

640

N

2

3

0

1016

USACO_1.4-4:Mother's Milk 母亲的牛奶

农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数. 最初，A和B桶都是空的，而C桶是装满牛奶的。有时，约翰把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。 写一个程序去帮助约翰找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。

单独的一行包括三个整数A,B和C。

只有一行，升序地列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。

8 9 10

1 2 8 9 10

0

USACO_1.4-4

2017-03-18 11:12:04

1

64

N

0

3

0

1017

USACO_1.5-1:Number Triangles 数字金字塔

考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和:30

第一个行包含 R(1<= R<=1000) ,表示行的数目。 后面每行为这个数字金字塔特定行包含的整数。 所有的被供应的整数是非负的且不大于100。

单独的一行包含那个可能得到的最大的和。

5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

30

0

很奇怪的问题再次出现，本题共9组数据，我的程序放上去的8组数据都没有问题，只有最后一组数据报出Wrong Answer 最后一组数据规模较大，为上限：1000 但我的程序应问题不大，毕竟是在USACO上通过的！

USACO_1.5-1

2017-03-18 11:12:04

5

64

N

2

5

0

1018

USACO_1.5-2:Prime Palindromes 回文质数

因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 号是回文质数。 写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)间的所有回文质数;

第 1 行: 二个整数 a 和 b .

输出一个回文质数的列表，一行一个。

5 500

5 7 11 101 131 151 181 191 313 353 373 383

0

USACO_1.5-2

2017-03-18 11:12:04

1

64

N

3

6

0

1019

USACO_1.5-3:Superprime Rib 特殊的质数肋骨

农民约翰的母牛总是生产出最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。 农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说: 7 3 3 1 全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。 7331 被叫做长度 4 的特殊质数。 写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。数字1不被看作一个质数。

单独的一行包含N。

按顺序输出长度为 N 的特殊质数,每行一个。

4

2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393

0

USACO_1.5-3

2017-03-18 11:12:04

1

64

N

10

11

0

1020

（图挂了）USACO_1.5-4:Checker Challenge 跳棋的挑战

检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行，每列，每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子。 列号 <img border="0" src="http://60.191.162.158:8080/JudgeOnline/images/p1020.jpg" /> 上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下： 行号 1 2 3 4 5 6 列号 2 4 6 1 3 5 这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。 特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出，这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号将被无警告删除

一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

6

2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4

0

USACO_1.5-4

2017-07-20 15:39:46

1

64

N

0

3

0

1021

USACO教程：Complete Search枚举搜索

思想： 写枚举搜索时应遵循KISS原则（Keep it simple stupid，译为“写最单纯愚蠢的程序”，意思是应把程序写得尽量简洁），竞赛时写程序的最终目标就是在限制时间内求出解，而不需太在意否还有更快的算法。 枚举搜索具有强大的力量，他用直接面向答案并尝试所有方案的方法发现答案。这种算法几乎总是解题时你第一个想到的方法。如果它能在规定的时间与空间限制内找出解，那么它常常很容易编写与调试。这就意味着你可以有时间去解答其他难题，即那些不能显示枚举算法强大的题目。 如果你面对一道可能状态小于两百万的题目，那么你可以考虑使用枚举搜索。尝试所有的状态，看看它们是否可行。 小心！小心！ 有时，题目不会直接要求你使用枚举算法。 例题1：派对灯 [IOI 98] 在一次IOI派对上有N个灯和4个灯开光，第一个开关可以使所有灯改变状态（关上开着的灯，开启关着的灯），第二个开关可以改变所有偶数位上灯的状态，第三个开关可以改变所有奇数位上灯的状态，第四个开关控制着灯1、4、7、10……（3n+1）。 告诉你N的值和所有按开关的次数（小于10,000次）。并告诉你某些灯的状态（例如：7号灯是关着的，10号灯是开着的）请编程输出所有灯可能的最后状态。 很明显，每次按开关你都要偿试4种可能。那么总共要试 410000 次（大约 106020），那意味着你没有足够的时间去使用枚举搜索，但是我们将枚举方法改进一下，那就可以使用枚举了。因为无论有多少个灯，由于开关控制的特殊性，都会出现6个灯一次循环的情况，即1号灯的状态永远与7号灯，13号灯，19号灯……相同，2号灯的状态也永远与8号灯，14号灯，20号灯……相同。同样，无论你按了多少次开关，按同一个开关两次就相当于没有按该开关，那么每一个开关就只需要考虑按一次或没有按，那么这题的枚举量就很小了。 例题2: 时钟调整 [IOI 94] 有九个钟被摆放在一个3 X 3的矩阵中，它们各自指向12：00，9：00，6：00，3：00中的一种，你的目的是将它们的指针全部调向12：00。很遗憾，每一次调整你都只能从九种调整方案中选择一种执行（九种方案已被从1到9编号），每一种方案可以改变固定钟的状态（例如：方案1控制钟1，2，3，方案2控制钟1，4，7，方案3控制钟5，6，8，9……），即将方案指定的所有钟向前拨快3小时（使时针向顺时针方向旋转90度），请你输出一个数列，使得按该数列表示方案执行后，所有钟都指向12：00。并且如果把整个序列看作一个数，要求该数最小。 最容易想到的方法是用递归枚举1到9的方案在该步使用。很可怕，由于递归的层数在此没有限定，所以将用掉 9k 的时间（k为层数），那可能是相当巨大的。其实，不用紧张，细心的你一定会发现：当一个方案执行4次后，就相当于没有执行，又因为题目要求输出最优解，那么任意一个方案都没有必要4次以上执行。也就是说，只需要枚举每一个方案的4种情况（没执行，执行1，2，3次）就可以了。他仅有49 ，约262,072此枚举，我们的计算机1s内就可以算完，应该算是极快了。 类似问题： 挤牛奶 [USACO 1996 初赛] 给出一个挤牛奶的顺序（农夫 A 在 300 秒到 1000秒时挤牛奶, 农夫 B从 700 秒到 1200秒），要求输出： 最长的有人挤牛奶的时间。 最长的没人挤牛奶的时间。 完全数牛与完全数牛群 [USACO 1995 决赛] 如果一个数可以由它的某几个约数相加得到，那么我们叫它完全数，如28 = 1 + 2 + 4 + 7 + 14。而一对完全对数就是指两个数都可以由对方的约数相加得出。同样一个完全数组就是一个数组的第一个数可以由第二个数的约数加和得到，第二个数也可以由第三个数的约数相加得到……最后一个数可以由第一个数的约数加和得到。 现在Farmer John已经将它的牛儿们编好了号（1到32000）请找出其中所有的完全数牛与完全数牛群。

Complete Search The Idea Solving a problem using complete search is based on the ``Keep It Simple, Stupid'' principle. The goal of solving contest problems is to write programs that work in the time allowed, whether or not there is a faster algorithm. Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer. This method should almost always be the first algorithm/solution you consider. If this works within time and space constraints, then do it: it's easy to code and usually easy to debug. This means you'll have more time to work on all the hard problems, where brute force doesn't work quickly enough. In the case of a problem with only fewer than a couple million possibilities, iterate through each one of them, and see if the answer works. Careful, Careful Sometimes, it's not obvious that you use this methodology. Problem: Party Lamps [IOI 98] You are given N lamps and four switches. The first switch toggles all lamps, the second the even lamps, the third the odd lamps, and last switch toggles lamps 1, 4, 7, 10, ... . Given the number of lamps, N, the number of button presses made (up to 10,000), and the state of some of the lamps (e.g., lamp 7 is off), output all the possible states the lamps could be in. Naively, for each button press, you have to try 4 possibilities, for a total of 410000 (about 106020 ), which means there's no way you could do complete search (this particular algorithm would exploit recursion). Noticing that the order of the button presses does not matter gets this number down to about 100004 (about 1016 ), still too big to completely search (but certainly closer by a factor of over 106000 ). However, pressing a button twice is the same as pressing the button no times, so all you really have to check is pressing each button either 0 or 1 times. That's only 24 = 16 possibilities, surely a number of iterations solvable within the time limit. Problem 3: The Clocks [IOI 94] A group of nine clocks inhabits a 3 x 3 grid; each is set to 12:00, 3:00, 6:00, or 9:00. Your goal is to manipulate them all to read 12:00. Unfortunately, the only way you can manipulate the clocks is by one of nine different types of move, each one of which rotates a certain subset of the clocks 90 degrees clockwise. Find the shortest sequence of moves which returns all the clocks to 12:00. The ``obvious'' thing to do is a recursive solution, which checks to see if there is a solution of 1 move, 2 moves, etc. until it finds a solution. This would take 9k time, where k is the number of moves. Since k might be fairly large, this is not going to run with reasonable time constraints. Note that the order of the moves does not matter. This reduces the time down to k9 , which isn't enough of an improvement. However, since doing each move 4 times is the same as doing it no times, you know that no move will be done more than 3 times. Thus, there are only 49 possibilities, which is only 262,072, which, given the rule of thumb for run-time of more than 10,000,000 operations in a second, should work in time. The brute-force solution, given this insight, is perfectly adequate. Sample Problems Milking Cows [USACO 1996 Competition Round] Given a cow milking schedule (Farmer A milks from time 300 to time 1000, Farmer B from 700 to 1200, etc.), calculate The longest time interval in which at least one cow was being milked The longest time interval in which no cow is being milked Perfect Cows & Perfect Cow Cousins [USACO 1995 Final Round] A perfect number is one in which the sum of the proper divisors add up to the number. For example, 28 = 1 + 2 + 4 + 7 + 14. A perfect pair is a pair of numbers such that the sum of the proper divisor of each one adds up to the other. There are, of course, longer perfect sets, such that the sum of the divisors of the first add up to the second, the second's divisors to the third, etc., until the sum of the last's proper divisors add up to the first number. Each cow in Farmer John's ranch is assigned a serial number. from 1 to 32000. A perfect cow is one which has a perfect number as its serial. A group of cows is a set of perfect cow cousins if their serial numbers form a perfect set. Find all perfect cows and perfect cow cousins.

0

2017-03-18 11:19:08

1

64

N

3

3

0

1022

USACO教程：Greedy Algorithm贪心算法

样例：牛棚修理 [1999 USACO 春季公开赛] Farmer John 有一列牛棚，在一次暴风中，牛棚的一整面墙都被吹倒了，但还好不是每一间牛棚都有牛。Farmer John 决定卖木料来修理牛棚，然而，刻薄的木材提供商却只能提供有限块的木料（木料的长度不限），现在告诉你关着牛的牛棚号，和提供的木材个数N，你的任务是编程求出最小的木块长度和。（1 <= N <= 50） 贪心思想： 贪心思想的本质是每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。例如：在样例中，若已经发现 N = 5 时的最优解，那么我们可以直接利用 N = 5 的最优解构成 N = 4 的最优解，而不用去考虑那些 N = 4 时的其他非最优解。 贪心算法的最大特点就是快。通常，二次方级的存储要浪费额外的空间，而且很不幸，那些空间经常得不出正解。但是，当使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。 贪心的难点： 贪心算法有两大难点： 如何贪心： 怎样才能从众多可行解中找到最优解呢？其实，大部分都是有规律的。在样例中，贪心就有很明显的规律。但你得到了 N = 5 时的最优解后，你只需要在已用上的5块木板中寻找最靠近的两块，然后贴上中间的几个牛棚，使两块木板变成一块。这样生成的 N = 4 的解必定最优。因为这样木板的浪费最少。同样，其他的贪心题也会有这样的性质。正因为贪心有如此性质，它才能比其他算法要快。 贪心的正确性： 要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。一个你想出的贪心性质也许是错的，即使它在大部分数据中都是可行的，你必须考虑到所有可能出现的特殊情况，并证明你的贪心性质在这些特殊情况中仍然正确。这样经过千锤百炼的性质才能构成一个正确的贪心。 在样例中，我们的贪心性质是正确的。如下： 假设我们的答案盖住了较大的空牛棚连续列，而不是较小的。那么我们把那部分盖空牛棚的木板锯下来，用来把较小的空牛棚连续列盖住，还会有剩余。那么锯掉它们！还给木材商！同时我们的解也变小了。也就是说，我们获得更优的解。所以，靠盖住较大空牛棚连续列的方法无法获得最优解，我们也应该尽量贪心那些距离小的木板合并。 如果仍有一个空牛棚连续列与我们的答案盖住的那个相同，我们同样使用上述的方法。会发现获得的新解与原解相同，那么不论我们选哪个，结果都将一样。 由此可见，如果我们合并的两块木板间距离最短，那么总能获得最优解。所以，在解题的每一步中，我们都只需要寻找两块距离最小的木板并合并它们。这样，我们获得的解必定最优。 结论： 如果有贪心性质存在，那么一定要采用！因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，它是所有算法中最好的。但是应该注意，别陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好还是不要冒险，因为还有其他算法会比它要保险。 类似问题： 三值排序问题 [IOI 1996] 有一个由N个数值均为1、2或3的数构成的序列（N<= 1000），其值无序，现要求你用最少的交换次数将序列按升序顺序排列。 算法：排序后的序列分为三个部分：排序后应存储1的部分，排序后应存储2的部分和排序后应存储3的部分，贪心排序法应交换尽量多的交换后位置正确的（2，1）、（3，1）和（3，2）数对。当这些数对交换完毕后，再交换进行两次交换后位置正确的（1，2，3）三个数。 分析：很明显，每一次交换都可以改变两个数的位置，若经过一次交换以后，两个数的位置都由错误变为了正确，那么它必定最优。同时我们还可发现，经过两次交换后，我们可以随意改变3个数的位置。那么如果存在三个数恰好为1，2和3，且位置都是错误的，那么进行两次交换使它们位置正确也必定最优。有由于该题具有最优子结构性质，我们的贪心算法成立。 货币系统 -- 一个反例 [已删节] 奶牛王国刚刚独立，王国中的奶牛们要求设立一个货币系统，使得这个货币系统最好。现在告诉你一个货币系统所包含的货币面额种类（假设全为硬币）以及所需要找的钱的大小，请给出用该货币系统找出该钱数，并且要求硬币数尽量少。 算法：每次都选择面额不超过剩余钱数但却最大的一枚硬币。例如：有货币系统为{1，2，5，10}，要求找出16，那么第一次找出10，第二次找出5，第三次找出1，恰好为最优解。 错误分析: 其实可以发现，这种算法并不是每一次都能构成最优解。反例如：货币系统{1，5，8，10}，同样找16，贪心的结果是10，5，1三枚，但用两枚8的硬币才是最优解。因为这样，贪心的性质不成立，如此解题也是错的。 拓扑排序 给你一些物品的集合，然后给你一些这些物品的摆放顺序的约束，如"物品A应摆放在物品B前"，请给出一个这些物品的摆放方案，使得所有约束都可以得到满足。 算法：对于给定的物品创建一个有向图，A到B的弧表示"物品A应摆放在物品B前”。以任意顺序对每个物品进行遍历。每当你找到一个物品，他的入度为0，那么贪心地将它放到当前序列的末尾，删除它所有的出弧，然后对它的出弧指向的所有结点进行递归，用同样的算法。如果这个算法遍历了所有的物品，但却没有把所有的物品排序，那就意味着没有满足条件的解。

Greedy Algorithm Greedy Algorithm Sample Problem: Barn Repair [1999 USACO Spring Open] There is a long list of stalls, some of which need to be covered with boards. You can use up to N (1 <= N <= 50) boards, each of which may cover any number of consecutive stalls. Cover all the necessary stalls, while covering as few total stalls as possible. The Idea The basic idea behind greedy algorithms is to build large solutions up from smaller ones. Unlike other approaches, however, greedy algorithms keep only the best solution they find as they go along. Thus, for the sample problem, to build the answer for N = 5, they find the best solution for N = 4, and then alter it to get a solution for N = 5. No other solution for N = 4 is ever considered. Greedy algorithms are fast, generally linear to quadratic and require little extra memory. Unfortunately, they usually aren't correct. But when they do work, they are often easy to implement and fast enough to execute. Problems There are two basic problems to greedy algorithms. How to Build How does one create larger solutions from smaller ones? In general, this is a function of the problem. For the sample problem, the most obvious way to go from four boards to five boards is to pick a board and remove a section, thus creating two boards from one. You should choose to remove the largest section from any board which covers only stalls which don't need covering (so as to minimize the total number of stalls covered). To remove a section of covered stalls, take the board which spans those stalls, and make into two boards: one of which covers the stalls before the section, one of which covers the stalls after the section. Does it work? The real challenge for the programmer lies in the fact that greedy solutions don't always work. Even if they seem to work for the sample input, random input, and all the cases you can think of, if there's a case where it won't work, at least one (if not more!) of the judges' test cases will be of that form. For the sample problem, to see that the greedy algorithm described above works, consider the following: Assume that the answer doesn't contain the large gap which the algorithm removed, but does contain a gap which is smaller. By combining the two boards at the end of the smaller gap and splitting the board across the larger gap, an answer is obtained which uses as many boards as the original solution but which covers fewer stalls. This new answer is better, so therefore the assumption is wrong and we should always choose to remove the largest gap. If the answer doesn't contain this particular gap but does contain another gap which is just as large, doing the same transformation yields an answer which uses as many boards and covers as many stalls as the other answer. This new answer is just as good as the original solution but no better, so we may choose either. Thus, there exists an optimal answer which contains the large gap, so at each step, there is always an optimal answer which is a superset of the current state. Thus, the final answer is optimal. Conclusions If a greedy solution exists, use it. They are easy to code, easy to debug, run quickly, and use little memory, basically defining a good algorithm in contest terms. The only missing element from that list is correctness. If the greedy algorithm finds the correct answer, go for it, but don't get suckered into thinking the greedy solution will work for all problems. Sample Problems Sorting a three-valued sequence [IOI 1996] You are given a three-valued (1, 2, or 3) sequence of length up to 1000. Find a minimum set of exchanges to put the sequence in sorted order. Algorithm The sequence has three parts: the part which will be 1 when in sorted order, 2 when in sorted order, and 3 when in sorted order. The greedy algorithm swaps as many as possible of the 1's in the 2 part with 2's in the 1 part, as many as possible 1's in the 3 part with 3's in the 1 part, and 2's in the 3 part with 3's in the 2 part. Once none of these types remains, the remaining elements out of place need to be rotated one way or the other in sets of 3. You can optimally sort these by swapping all the 1's into place and then all the 2's into place. Analysis: Obviously, a swap can put at most two elements in place, so all the swaps of the first type are optimal. Also, it is clear that they use different types of elements, so there is no ``interference'' between those types. This means the order does not matter. Once those swaps have been performed, the best you can do is two swaps for every three elements not in the correct location, which is what the second part will achieve (for example, all the 1's are put in place but no others; then all that remains are 2's in the 3's place and vice-versa, and which can be swapped). Friendly Coins - A Counterexample [abridged] Given the denominations of coins for a newly founded country, the Dairy Republic, and some monetary amount, find the smallest set of coins that sums to that amount. The Dairy Republic is guaranteed to have a 1 cent coin. Algorithm: Take the largest coin value that isn't more than the goal and iterate on the total minus this value. (Faulty) Analysis: Obviously, you'd never want to take a smaller coin value, as that would mean you'd have to take more coins to make up the difference, so this algorithm works. Maybe not: Okay, the algorithm usually works. In fact, for the U.S. coin system {1, 5, 10, 25}, it always yields the optimal set. However, for other sets, like {1, 5, 8, 10} and a goal of 13, this greedy algorithm would take one 10, and then three 1's, for a total of four coins, when the two coin solution {5, 8} also exists. Topological Sort Given a collection of objects, along with some ordering constraints, such as "A must be before B," find an order of the objects such that all the ordering constraints hold. Algorithm: Create a directed graph over the objects, where there is an arc from A to B if "A must be before B." Make a pass through the objects in arbitrary order. Each time you find an object with in-degree of 0, greedily place it on the end of the current ordering, delete all of its out-arcs, and recurse on its (former) children, performing the same check. If this algorithm gets through all the objects without putting every object in the ordering, there is no ordering which satisfies the constraints.

0

2017-03-18 11:19:08

1

64

N

4

4

0

1023

USACO教程：Search Techniques搜索方式

样例: n 皇后问题 [经典问题] 将 n 个皇后摆放在一个 n x n 的棋盘上，使得每一个皇后都无法攻击到其他皇后。 深度优先搜索 (DFS) 显而易见，最直接的方法就是把皇后一个一个地摆放在棋盘上的合法位置上，枚举所有可能寻找可行解。可以发现在棋盘上的每一行（或列）都存在且仅存在一个皇后，所以，在递归的每一步中，只需要在当前行(或列）中寻找合法格，选择其中一个格摆放一个皇后。 1 search(col) 2 if filled all columns 3 print solution and exit 4 for each row 5 if board(row, col) is not attacked 6 place queen at (row, col) 7 search(col+1) 8 remove queen at (row, col) 从search(0)开始搜索，由于在每一步中可选择的节点较少，该方法可以较快地求解：当一定数量的皇后被摆放在棋盘上后那些不会被攻击到的节点的数量将迅速减少。 这是深度优先搜索的一个经典例题，该算法总是能尽可能快地抵达搜索树的底层：当 k 个皇后被摆放到棋盘上时，可以马上确定如何在棋盘上摆放下一个皇后，而不需要去考虑其他的顺序摆放皇后可能造成的影响（如当前情况是否为最优情况），该方法有时可以在找到可行解之前避免复杂的计算，这是十分值得的。 深度优先搜索具有一些特性，考虑下图的搜索树： <img border=0 src=http://60.191.162.158:8080/JudgeOnline/images/p1023rec1.gif> 该算法用逐步加层的方法搜索并且适当时回溯，在每一个已被访问过的节点上标号，以便下次回溯时不会再次被搜索。绘画般地，搜索树将以如下顺序被遍历： <img border=0 src=http://60.191.162.158:8080/JudgeOnline/images/p1023rec2.gif> 复杂度： 假设搜索树有 d 层（在样例中 d=n ，即棋盘的列数）。再假设每一个节点都有 c 个子节点（在样例中，同样 c=n ，即棋盘的行数，但最后一层没有子节点，除外）。那么整个搜索花去的时间将与 cd 成正比，是指数级的。但是其需要的空间较小，除了搜索树以外，仅需要用一个栈存储当前路径所经过的节点，其空间复杂度为 O(d) 。 样例：骑士覆盖问题[经典问题] 在一个 n x n 的棋盘中摆放尽量少的骑士，使得棋盘的每一格都会被至少一个骑士攻击到。但骑士无法攻击到它自己站的位置. 广度优先搜索 (BFS) 在这里，最好的方法莫过于先确定 k 个骑士能否实现后再尝试 k+1 个骑士，这就叫广度优先搜索。通常，广度优先搜索需用队列来帮助实现。 1 process(state) 2 for each possible next state from this one 3 enqueue next state 4 search() 5 enqueue initial state 6 while !empty(queue) 7 state = get state from queue 8 process(state) 广度优先搜索得名于它的实现方式：每次都先将搜索树某一层的所有节点全部访问完毕后再访问下一层, 再利用先前的那颗搜索树，广度优先搜索以如下顺序遍历： <img border=0 src=http://60.191.162.158:8080/JudgeOnline/images/p1023rec3.gif> 首先访问根节点，而后是搜索树第一层的所有节点，之后第二层、第三层……以此类推。 复杂度： 广度优先搜索所需的空间与深度优先搜索所需的不同（ n 皇后问题的空间复杂度为 O(n) ）,广度优先搜索的空间复杂取决于每层的节点数。如果搜索树有 k 层，每个节点有 c 个子节点，那么最后将可能有 c k 个数据被存入队列，这个复杂度无疑是巨大的。所以在使用广度优先搜索时，应小心处理空间问题。 迭代加深搜索 (ID) 广度优先搜索可以用迭代加深搜索代替。迭代加深搜索实质是限定下界的深度优先搜索，即首先允许深度优先搜索搜索 k 层搜索树，若没有发现可行解，再将 k+1 后再进行一次以上步骤，直到搜索到可行解。这个“模仿广度优先搜索”搜索法比起广搜是牺牲了时间，但节约了空间。 1 truncated_dfsearch(hnextpos, depth) 2 if board is covered 3 print solution and exit 4 if depth == 0 5 return 6 for i from nextpos to n*n 7 put knight at i 8 truncated_dfsearch(i+1, depth-1) 9 remove knight at i 10 dfid_search 11 for depth = 0 to max_depth 12 truncated_dfsearch(0, depth) 复杂度： 　 ID时间复杂度与DFS的时间复杂度（O(n)）不同，另一方面，它要更复杂，某次DFS若限界 k 层，则耗时 ck 。若搜索树共有 d 层，则一个完整的DFS-ID将耗时 c0 + c1 + c2 + ... + cd 。如果 c = 2 ，那么式子的和是 cd+1 - 1 ，大约是同效BFS的两倍。当 c > 2 时（子节点的数目大于2），差距将变小：ID的时间消耗不可能大于同效BFS的两倍。 所以，但数据较大时，ID-DFS并不比BFS慢，但是空间复杂度却与DFS相同，比BFS小得多。 算法选择： 当你已经知道某题是一道搜索题，那么选择正确的搜索方式是十分重要的。下面给你一些选择的依据。 简表： 搜索方式 时间 空间 使用情况 DFS O(c k) O(k) 必须遍历整棵树，要求出解的深度或经的过节点，或者你并不需要解的深度最小。 BFS O(c d ) O(c d ) 了解到解十分靠近根节点，或者你需要解的深度最小。 DFS+ID O(c d) O(d) 需要做BFS，但没有足够的空间，时间却很充裕。 d ：解的深度 k ：搜索树的深度 d <= k 记住每一种搜索法的优势。如果要求求出最接近根节点的解，则使用BFD或ID。而如果是其他的情况，DFS是一种很好的搜索方式。如果没有足够的时间搜出所有解。那么使用的方法应最容易搜出可行解，如果答案可能离根节点较近，那么就应该用BFS或ID，相反，如果答案离根节点较远，那么使用DFS较好。还有，请仔细小心空间的限制。如果空间不足以让你使用BFS，那么请使用迭代加深吧！ 类似问题： 超级质数肋骨[USACO 1994 决赛] 一个数，如果它从右到左的一位、两位直到N位（N是）所构成的数都是质数，那么它就称为超级质数。例如：233、23、2都是质数，所以233是超级质数。要求：读入一个数N（N <= 9），编程输出所有有N位的超级质数。 这题应使用DFS，因为每一个答案都有N层（最底层），所以DFS是最好的． Betsy的旅行 [USACO 1995 资格赛] 一个正方形的小镇被分成 NxN (2 <= N <= 6）个小方格，Besty 要从左上角的方格到达左下角的方格，并且经过每一次方格都恰好经过一次。编程对于给定的 N 计算出 Besty 能采用的所有的旅行路线的数目。 这题要求求出解的数量，所以整颗搜索树都必须被遍历，这就与可行解的位置与出解速度没有关系了。所以这题可以使用BFS或DFS，又因为DFS需要的空间较少，所以DFS是较好的． 奶牛运输 [USACO 1995 决赛] 奶牛运输公司拥有一辆运输卡车与牧场 A ，运输公司的任务是在A，B，C，D，E，F和G七个农场之间运输奶牛。每两个农场之间的路程（可以用floyed改变）已给出。每天早晨，运输公司都必须确定一条运输路线，使得运输的总距离最短。但必须遵守以下规则： 农场 A 是公司的基地。每天的运输都必须从这开始并且在这结束。 卡车任何时刻都只能最多承载一头奶牛。 给出的数据是奶牛的原先位置与运输结束后奶牛所在的位置。 而你的任务是在上述规则内寻找最短的运输路线。 在发现最优解时必须比较所有可行解，所以必须遍历整棵搜索树。所以，可以用DFS解题． 横越沙漠 [1992 IOI] 一群沙漠探险者正尝试着让他们中的一部分人横渡沙漠。每一个探险者可以携带一定数量的水，同时他们每天也要喝掉一定量的水。已知每个探险者可携带的水量与每天需要的水量都不同。给出每个探险者能携带的水量与需要的水量与横渡沙漠所需的天数，请编程求出最多能有几个人能横渡沙漠。所有探险者都必须存活，所以有些探险者在中途必须返回，返回时也必须携带足够的水。当然，如果一个探险者返回时有剩余的水（除去返回所需的水以外），他可以把剩余的水送给他的一个同伴，如果它的同伴可以携带的话。 这题可以分成两个小问题，一个是如何为探险者分组，另一个是某些探险者应在何处返回。所以使用ID-DFS是可行的。首先尝试每一个探险者能否独自横渡，然后是两个人配合，三个人配合。直到结束。

Crafting Winning Solutions A good way to get a competitive edge is to write down a game plan for what you're going to do in a contest round. This will help you script out your actions, in terms of what to do both when things go right and when things go wrong. This way you can spend your thinking time in the round figuring out programming problems and not trying to figure out what the heck you should do next... it's sort of like precomputing your reactions to most situations. Mental preparation is also important. Game Plan For A Contest Round Read through ALL the problems FIRST; sketch notes with algorithm, complexity, the numbers, data structs, tricky details, ... Brainstorm many possible algorithms - then pick the stupidest that works! DO THE MATH! (space & time complexity, and plug in actual expected and worst case numbers) Try to break the algorithm - use special (degenerate?) test cases Order the problems: shortest job first, in terms of your effort (shortest to longest: done it before, easy, unfamiliar, hard) Coding a problem - For each, one at a time: Finalize algorithm Create test data for tricky cases Write data structures Code the input routine and test it (write extra output routines to show data?) Code the output routine and test it Stepwise refinement: write comments outlining the program logic Fill in code and debug one section at a time Get it working & verify correctness (use trivial test cases) Try to break the code - use special cases for code correctness Optimize progressively - only as much as needed, and keep all versions (use hard test cases to figure out actual runtime) Time management strategy and "damage control" scenarios Have a plan for what to do when various (foreseeable!) things go wrong; imagine problems you might have and figure out how you want to react. The central question is: "When do you spend more time debugging a program, and when do you cut your losses and move on?". Consider these issues: How long have you spent debugging it already? What type of bug do you seem to have? Is your algorithm wrong? Do you data structures need to be changed? Do you have any clue about what's going wrong? A short amount (20 mins) of debugging is better than switching to anything else; but you might be able to solve another from scratch in 45 mins. When do you go back to a problem you've abandoned previously? When do you spend more time optimizing a program, and when do you switch? Consider from here out - forget prior effort, focus on the future: how can you get the most points in the next hour with what you have? Have a checklist to use before turning in your solutions: Code freeze five minutes before end of contest? Turn asserts off. Turn off debugging output. Tips & Tricks Brute force it when you can KISS: Simple is smart! Hint: focus on limits (specified in problem statement) Waste memory when it makes your life easier (if you can get away with it) Don't delete your extra debugging output, comment it out Optimize progressively, and only as much as needed Keep all working versions! Code to debug: whitespace is good, use meaningful variable names, don't reuse variables, stepwise refinement, COMMENT BEFORE CODE. Avoid pointers if you can Avoid dynamic memory like the plague: statically allocate everything. Try not to use floating point; if you have to, put tolerances in everywhere (never test equality) Comments on comments: Not long prose, just brief notes Explain high-level functionality: ++i; /* increase the value of i by */ is worse than useless Explain code trickery Delimit & document functional sections As if to someone intelligent who knows the problem, but not the code Anything you had to think about Anything you looked at even once saying, "now what does that do again?" Always comment order of array indices Keep a log of your performance in each contest: successes, mistakes, and what you could have done better; use this to rewrite and improve your game plan! Complexity Basics and order notation The fundamental basis of complexity analysis revolves around the notion of ``big oh'' notation, for instance: O(N). This means that the algorithm's execution speed or memory usage will double when the problem size doubles. An algorithm of O(N 2) will run about four times slower (or use 4x more space) when the problem size doubles. Constant-time or space algorithms are denoted O(1). This concept applies to time and space both; here we will concentrate discussion on time. One deduces the O() run time of a program by examining its loops. The most nested (and hence slowest) loop dominates the run time and is the only one mentioned when discussing O() notation. A program with a single loop and a nested loop (presumably loops that execute N times each) is O(N 2), even though there is also a O(N) loop present. Of course, recursion also counts as a loop and recursive programs can have orders like O(b N), O(N!), or even O(N N). Rules of thumb When analyzing an algorithm to figure out how long it might run for a given dataset, the first rule of thumb is: modern (2004) computers can deal with 100M actions per second. In a five second time limit program, about 500M actions can be handled. Really well optimized programs might be able to double or even quadruple that number. Challenging algorithms might only be able to handle half that much. Current contests usually have a time limit of 1 second for large datasets. 16MB maximum memory use 210 ~approx~ 10 3 If you have k nested loops running about N iterations each, the program has O(N k) complexity. If your program is recursive with b recursive calls per level and has l levels, the program O(b l) complexity. Bear in mind that there are N! permutations and 2 n subsets or combinations of N elements when dealing with those kinds of algorithms. The best times for sorting N elements are O(N log N). DO THE MATH! Plug in the numbers. Examples A single loop with N iterations is O(N): 1 sum = 0 2 for i = 1 to n 3 sum = sum + i A double nested loop is often O(N 2): # fill array a with N elements 1 for i = 1 to n-1 2 for j = i + 1 to n 3 if (a[i] > a[j]) swap (a[i], a[j]) Note that even though this loop executes N x (N+1) / 2 iterations of the if statement, it is O(N 2) since doubling N quadruples the execution times. Consider this well balanced binary tree with four levels: An algorithm that traverses a general binary tree will have complexity O(2 N). Solution Paradigms Generating vs. Filtering Programs that generate lots of possible answers and then choose the ones that are correct (imagine an 8-queen solver) are filters. Those that hone in exactly on the correct answer without any false starts are generators. Generally, filters are easier (faster) to code and run slower. Do the math to see if a filter is good enough or if you need to try and create a generator. Precomputation Sometimes it is helpful to generate tables or other data structures that enable the fastest possible lookup of a result. This is called precomputation (in which one trades space for time). One might either compile precomputed data into a program, calculate it when the program starts, or just remember results as you compute them. A program that must translate letters from upper to lower case when they are in upper case can do a very fast table lookup that requires no conditionals, for example. Contest problems often use prime numbers - many times it is practical to generate a long list of primes for use elsewhere in a program. Decomposition (The Hardest Thing At Programming Contests) While there are fewer than 20 basic algorithms used in contest problems, the challenge of combination problems that require a combination of two algorithms for solution is daunting. Try to separate the cues from different parts of the problem so that you can combine one algorithm with a loop or with another algorithm to solve different parts of the problem independently. Note that sometimes you can use the same algorithm twice on different (independent!) parts of your data to significantly improve your running time. Symmetries Many problems have symmetries (e.g., distance between a pair of points is often the same either way you traverse the points). Symmetries can be 2-way, 4-way, 8-way, and more. Try to exploit symmetries to reduce execution time. For instance, with 4-way symmetry, you solve only one fourth of the problem and then write down the four solutions that share symmetry with the single answer (look out for self-symmetric solutions which should only be output once or twice, of course). Forward vs. Backward Surprisingly, many contest problems work far better when solved backwards than when using a frontal attack. Be on the lookout for processing data in reverse order or building an attack that looks at the data in some order or fashion other than the obvious. Simplification Some problems can be rephrased into a somewhat different problem such that if you solve the new problem, you either already have or can easily find the solution to the original one; of course, you should solve the easier of the two only. Alternatively, like induction, for some problems one can make a small change to the solution of a slightly smaller problem to find the full answer.

0

2017-03-18 11:19:08

1

64

N

3

3

0

1024

USACO_2.1-1:The Castle城堡IOI'94-Day1

以一个几乎超乎想像的运气，农民约翰在他的生日收到了一张爱尔兰博彩的奖券。 这一张奖券成为了唯一中奖的奖券。 农民约翰嬴得爱尔兰的乡下地方的一个传说中的城堡。 吹牛在他们威斯康辛州不算什么，农民约翰想告诉他的牛所有有关城堡的事。 他想知道城堡有多少房间，而且最大的房间有多大。 事实上，他想去掉一面墙来制造一个更大的房间。 你的任务是帮助农民约翰去了解正确房间数目和大小。 城堡的平面图被分为 M(wide)*N(1 <=M,N<=50)个小正方形。 每个这样的小正方形有0到4面墙。 城堡在它的外部边缘总是有墙壁的，好遮挡风雨。 考虑这注解了一个城堡的平面图：<img src="/JudgeOnline/upload/image/20170720/20170720153417_64213.png" alt="" />例子的城堡的大小是7 x 4。 一个 "房间"是平面图上有连接的"小正方形"的集合。 这个平面图包含五个房间。(它们的大小是9,7,3,1, 和 8 排列没有特别的顺序)。 移除被箭作记号的墙壁来合并两个房间来制造最大的可能房间(移除一面墙所能产生的)。 城堡总是至少有二个房间并且总是有一面墙壁以可能被移除。

地图以一个表格来储存，每个数字描述一个小正方形，N行每行M个数来描述这个平面图。 输入顺序符合那个在上面例子的编号方式。 每个描述小正方形的数字说明小正方形的四面的墙的分布情况，它是下面4个数的和： 1: 在西面有墙 2: 在北面有墙 4: 在东面有墙 8: 在南面有墙 内部的墙壁是会被定义两次；小正方形(1,1)南面的墙也被指出是小正方形(2,1)北面的墙。 第 1 行: 二个被空格分开的整数: M 和 N 第 2 到 N+1 行: M x N 个整数,每行M个。

输出包含一些行: 第 1 行: 城堡的房间数目。 第 2 行: 最大的房间的大小 第 3 行: 移除一面墙能得到的最大的房间的大小 第 4 行: 移除哪面墙 选择最佳的墙来移除，(选择最靠西的，如果仍然不能确定，再选择最靠南的。编者注：墙的位置应该由它的中点来定义) (【原文】Choose the optimal wall to remove from the set of optimal walls by choosing the wall farther to the west (and then, if still tied, farthest to the south).) 墙壁由它在相邻的小正方形的西部或南方来命名

7 4 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13

5 9 16 4 1 E

0

USACO_2.1-1

2017-07-20 15:34:23

1

64

N

2

3

0

1025

USACO_2.1-2:Ordered Fractions顺序的分数

输入一个自然数N　 请写一个程序来增序输出分母小于等于N的既约真分数

单独的一行　一个自然数N(1..160)

每个分数单独占一行

5

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

0

USACO_2.1-2

2017-03-18 11:19:08

1

64

N

1

3

0

1026

TJU_P1001:排版题.输出排列成菱形的字母

输入N值，编程输出如下图形。

一个整数N（1<=N<=7）。

排列成菱形的大写字符，首字符为Z，以后依次为Y,X...

3

Z Y X W V U T S

0

TJU_P1001

2017-03-18 11:19:08

1

64

N

0

1

0

1027

选自黄皮书：排版题.输出排列成三角形的字母

输入一个N（1<=N<=26），输出由大写字母构成的三角形，字母递增从A开始。 如：N＝3 A A B A B C

输入N（1<=N<=26）。

由大写字母构成的三角形。

3

A A B A B C

0

选自黄皮书

2017-03-18 11:19:08

1

64

N

0

2

0

1028

TJU_P1008:排版题.扬辉三角

输出扬辉三角

本题有测试数据，每组数据仅含一个整数N(N不大于34)。一组数据独占一行。

对于每一组数据，先输出一个 Case #: 其中#号代表第#组数据。接下来输出一个由数字组成的扬辉三角。一行中的数字之间用一个空格分开。行尾不要有多余的空格。 两组数据之间空开一行。

6 3

Case 1: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 Case 2: 1 1 1 1 2 1

0

TJU_P1008

2017-03-18 11:19:08

1

64

N

2

4

0

1029

TJU_P1009:排版题.蛇行矩阵

蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。

本题有多组数据，每组数据由一个正整数N组成。（N不大于100）

对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。 矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。

5

1 3 6 10 15 2 5 9 14 4 8 13 7 12 11

0

TJU_P1009

2017-03-18 11:19:08

1

64

N

2

4

0

1030

TJU_P1012:约瑟夫问题

将编号为1,2,...,N的N个人按顺时针方向围坐一圈，每人持有一个密码（10000以内的正整数）。一开始任选一个正整数作为报数上限值M，从第一个开始按顺时针方向自1开始报数，报到M时停止报数。报M的人出列，将他的密码作为新的M值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

本题有多组数据。 每组数据的第一行是两个整数N，M ; 其中N和M均大于0且小于100。 第二行是N个正整数，分别表示1到N个人持有的密码。 两组数据之间空开一行。

对每组数据，按离开的顺序输出他们的编号。数字之间用一个空格分开。每组数据独占一行输出。

7 20 3 1 7 2 4 8 4 4 3 1 2 3 4

6 1 4 7 2 3 5 3 2 1 4

0

TJU_P1012

2017-03-18 11:19:08

1

64

N

0

4

0

1031

TJU_P1007:Step.如何得到输入数据的结束

Step 大家好！我是kaikai。 在Online Judge上，有的题目具有不确定的数据量。并且也没有特别指出哪个符号是表示数据的结束。这种情况下如何才能正确的得到数据？ 使用EOF！对，你的想法是正确的。 while(scanf("%d",&a)!=EOF) { ... } 当然你也可以利用scanf的返回值。 while(scanf("%d",&a)==1) { ... } Free Pascal下面的代码： program p(Input,Output); begin while not seekeof(Input) do begin ... end; end. NOTE, SeekEof函数不是标准pascal函数库中的，使用SeekEof函数在GNU Pascal下不能通过编译。 这2种方法的效果是一样的。下面来试试看。 Program 对输入的整数求和。所有的整数都不大于100

整数若干。每行一个。

一个整数，表示所有输入整数的和。

1 3 2 5 7

18

0

Programming Steps

TJU_P1007

2017-03-18 12:03:24

1

64

N

3

4

0

1032

TJU_P1005:母牛生小牛

设有一头小母牛，从出生第四年起每年生一头小母牛，按此规律，第N年时有几头母牛？

本题有多组数据。每组数据只有一个整数N，独占一行。(1≤N≤50)

对每组数据，输出一个整数（独占一行）表示第N年时母牛的数量

1 4 5 20

1 2 3 872

0

TJU_P1005

2017-03-18 12:03:24

1

64

N

3

7

0

1033

TJU_P1006:敲七

输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）

一个整数N。(N不大于30000)

从小到大排列的不大于N的与7有关的数字，每行一个。

20

7 14 17

0

careful n!

TJU_P1006

2017-03-18 12:03:24

1

64

N

2

3

0

1034

TJU_P1004:防御导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在使用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

最多20个整数，分别表示导弹依次飞来的高度（雷达给出高度数据是不大于30000的正整数）

两个整数M和N。表示：这套系统最多能拦截 M 枚导弹，如果要拦截所有导弹最少要配备 N 套这种导弹系统。

300 250 275 252 200 138 245

5 2

0

TJU_P1004

2017-03-18 12:03:24

1

64

N

2

3

0

1035

TJU_P1010:数素数

素数是的只能被1和它本身整除的自然数。判断一个数是素数的方法是使用2到该数的平方根的素数除它，若有能整除的则该数不是素数。

本题有多组数据，每组数据由两个正整数M,N组成。（0＜M＜N＜1000000）

输出一个整数，表示介于M,N之间（包括M,N）的素数的数量。

5 10 1 3 6 8

2 2 1

0

TJU_P1010

2017-03-18 12:03:24

5

64

N

2

3

0

1036

TJU_P1002:全排序问题

将一个字符组全排序

一个长度小于10的字符串，该字符串由数字1～9组成。字符不会重复出现。

按数字在输入串中出现的次序从小到大的顺序输出该字符组的全排序

132

1 3 2 1 2 3 3 1 2 3 2 1 2 1 3 2 3 1

0

TJU_P1002

2017-03-18 12:03:24

5

64

N

1

5

0

1037

NOIP_2000.PJ1:计算器的改良

NCL是一家专门从事计算器改良与升级的实验室，最近该实验室收到了某公司所委托的一个任务： 需要在该公司某型号的计算器上加上解一元一次方程的功能。 实验室将这个任务交给了一个刚进入的新手ZL先生。 为了很好的完成这个任务,ZL先生首先研究了一些一元一次方程的实例： 4+3x=8 6a-5+1=2-2a -5+12Y=0 ZL先生被主管告之，在计算器上键入的一个一元一次方程中，只包含整数、小写字母 及十、一、＝这三个数学符号（当然，符号“一”既可作减号，也可作负号）。 方程中并没有括号，也没有除号，方程中的字母表示未知数。 问题求解： 编写程序，解输入的一元一次方程，将解方程的结果（精确至小数点后三位）输出至屏幕。 你可假设对键入的方程的正确性的判断是由另一个程序员在做，或者说可认为键入的一元一次方程均为合法的，且有唯一实数解。

一个字符串，表示求解的方程

<p> 解方程的结果（精确至小数点后三位） </p> <p> <br /> </p>

6a-5+1=2-2a

a=0.750

0

NOIP_2000.PJ1

2017-07-20 16:13:29

1

64

N

9

19

0

1038

NOIP_2000.PJ2:税收与补贴问题

每样商品的价格越低，其销量就会相应增大。 现已知某种商品的成本及其在若干价位上的销量（产品不会低于成本销售），并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后，销量以某固定数值递减。（我们假设价格及销售量都是整数） 对于某些特殊商品，不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。（所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币） 问题求解： 你是某家咨询公司的项目经理，现在你已经知道政府对某种商品的预期价格，以及在各种价位上的销售情况。 要求你确定政府对此商品是应收税还是补贴的最少金额（也为整数），才能使商家在这样一种政府预期的价格上，获取相对其他价位上的最大总利润。 总利润=单位商品利润*销量 单位商品利润=单位商品价格-单位商品成本（-税金 or +补贴）

输入的第一行为政府对某种商品的预期价， 第二行有两个整数，第一个整数为商品成本，第二个整数为以成本价销售时的销售量， 以下若干行每行都有两个整数，第一个为某价位时的单价，第二个为此时的销量， 以一行-1，-1表示所有已知价位及对应的销量输入完毕， 输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。

输出有两种情况： 若在政府预期价上能得到最大总利润，则输出一个单独的整数， 数的正负表示是补贴还是收税， 数的大小表示补贴或收税的金额最小值。 若有多解，取绝对值最小的输出。 如在政府预期价上不能得到最大总利润，则输出“NO SOLUTION”

31 28 130 30 120 31 110 -1 -1 15

4

0

NOIP_2000.PJ2

2017-03-18 12:03:24

1

64

N

4

5

0

1039

NOIP_2000.PJ3:乘积最大

今年是国际数学联盟确定的“2000——世界数学年”， 又恰逢我国著名数学家华罗庚先生诞辰90周年。 在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。 活动中，主持人给所有参加活动的选手出了这样一道题目: 设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分， 找出一种分法，使得这K+1个部分的乘积能够为最大。 同时，为了帮助选手能够正确理解题意， 主持人还举了如下的一个例子： 有一个数字串: 312， 当N=3，K=1时会有以下两种分法： 1）3*12=36 2）31*2=62 这时，符合题目要求的结果是： 31*2=62 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

程序的输入共有两行: 第一行共有2个自然数N,K (6<=N<=40，1<=K<=6) 第二行是一个K度为N的数字串。

结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。

4 2 1231

62

0

NOIP_2000.PJ3

2017-03-18 12:03:24

1

64

N

4

5

0

1040

NOIP_2000.PJ4:单词接龙

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们己知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙" 中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

输入的第一行为一个单独的整数n(n<=20）表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表来“龙”开头的字母。你可以假定以此字母开头的“龙" 一定存在。

只需输出以此字母开头的最长的“龙”的长度

5 at touch cheat choose tact a

23 （连成的“龙”为atoucheatactactouchoose）

0

NOIP_2000.PJ4

2017-03-18 12:03:24

1

64

N

4

7

0

1041

NOIP_2001.PJ1:数的计数

我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理 l•不作任何处理: 2•茬它的左边加上一个自然数，但该自然数不能超过原数的一半; 3•加上数后，继续按此规则进行处理，直到不能再而 自然数为止。

输入：6 （满足条件的数为616 26 126 36 136 (此部分不必输出) ）

输出：6

6

6

0

【高精度】

NOIP_2001.PJ1

2017-07-20 16:16:07

1

64

N

6

9

0

1042

NOIP_2001.PJ2:最大公约数与最小公倍数问题

输入二个正整数x0,y0(2≤x0≤100000，2≤y0≤1000000)，求出满足下列条件的P、Q的个数。 条件:1.P、Q是正整数 2.要求P、Q以xO为最大公约数，以yO为最小公倍数。 试求，满足条件的所有可能的两个正整数的个数。

一行，两个整数x0，y0

<p> 输出：<span style="color:#333333;font-family:"font-size:14px;background-color:#EEEEEE;">满足条件的所有可能的两个正整数的个数</span> </p> <p> <br /> </p>

3 60

4 说明：(不用输出)此时的 P Q 分别为， 3 60 15 12 12 15 60 3 所以，满足条件的所有可能的两个正整数的个数共4种。

0

NOIP_2001.PJ2

2017-07-20 16:21:39

1

64

N

5

7

0

1043

NOIP_2001.PJ3:求先序排列

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。

<span style="color:#200000;font-family:"font-size:14px;background-color:#FFFFFF;">一行，两个以空格隔开的字符串，分别表示中序和后序排列</span>

<p> <span style="color:#200000;font-family:"font-size:14px;background-color:#FFFFFF;"> 一个字符串，表示所求先序排列</span> </p>

BADC BDCA

ABCD

0

NOIP_2001.PJ3

2017-07-20 15:48:00

1

64

N

3

4

0

1044

NOIP_2001.PJ4:装箱问题

有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。

<p> 第一行，一个整数，表示箱子容量   </p> <p> 第二行，一个整数，表示有n个物品。 </p> <p>  接下来n行，分别表示这n个物品的各自体积。 </p>

一个整数，表示箱子剩余空间。

24 6 8 3 12 7 9 7

0

0

NOIP_2001.PJ4

2017-07-20 15:51:11

1

64

N

6

12

0

1045

NOIP_2002.PJ1:级数求和

已知：Sn= 1＋1／2＋1／3＋…＋1／n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。 现给出一个整数K（1<=k<=15），要求计算出一个最小的n；使得Sn＞K。

一个整数K

一个整数n

1

2

0

NOIP_2002.PJ1

2017-07-20 15:52:34

1

64

N

4

5

0

1046

NOIP_2002.PJ2:选数

已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为： 3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。 现在，要求你计算出和为素数共有多少种。 例如上例，只有一种的和为素数：3＋7＋19＝29）。